package com.leetcode.algorithm.y19.m01;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)884. 两句话中的不常见单词
 * (done)748. 最短完整词
 * (done)447. 回旋镖的数量
 * (done)202. 快乐数
 * (done)953. 验证外星语词典
 * @author: jie.deng
 * @time: 2019年1月29日 下午4:59:02
 */
public class MySolution0129 {
	
	/**
	 * 884. 两句话中的不常见单词
	 * 
     * 给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）
     * 
     * 如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。
     * 
     * 返回所有不常用单词的列表。
     * 
     * 您可以按任何顺序返回列表。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：A = "this apple is sweet", B = "this apple is sour"
     * 输出：["sweet","sour"]
     * 示例 2：
     * 
     * 输入：A = "apple apple", B = "banana"
     * 输出：["banana"]
     *  
     * 
     * 提示：
     * 
     * 0 <= A.length <= 200
     * 0 <= B.length <= 200
     * A 和 B 都只包含空格和小写字母。
	 * @param A
	 * @param B
	 * @return
	 */
	public String[] uncommonFromSentences(String A, String B) {
		Set<String> setA = new HashSet<String>();
		Set<String> setACommon = new HashSet<String>();
		String[] strs = A.split(" ");
		for (String str : strs) {
			if (!setA.add(str)) {
				setACommon.add(str);
			}
		}
		Set<String> setB = new HashSet<String>();
		Set<String> setBCommon = new HashSet<String>();
		strs = B.split(" ");
		for (String str : strs) {
			if (!setB.add(str)) {
				setBCommon.add(str);
			}
		}
		for (String str : setA) {
			if (setB.contains(str)) {
				setACommon.add(str);
			}
		}
		for (String str : setB) {
			if (setA.contains(str)) {
				setBCommon.add(str);
			}
		}

		setA.addAll(setB);
		setA.removeAll(setACommon);
		setA.removeAll(setBCommon);
		return setA.toArray(new String[setA.size()]);
	}
    
    /**
     * 748. 最短完整词
     * 
     * 如果单词列表（words）中的一个单词包含牌照（licensePlate）中所有的字母，那么我们称之为完整词。在所有完整词中，最短的单词我们称之为最短完整词。
     * 
     * 单词在匹配牌照中的字母时不区分大小写，比如牌照中的 "P" 依然可以匹配单词中的 "p" 字母。
     * 
     * 我们保证一定存在一个最短完整词。当有多个单词都符合最短完整词的匹配条件时取单词列表中最靠前的一个。
     * 
     * 牌照中可能包含多个相同的字符，比如说：对于牌照 "PP"，单词 "pair" 无法匹配，但是 "supper" 可以匹配。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
     * 输出："steps"
     * 说明：最短完整词应该包括 "s"、"p"、"s" 以及 "t"。对于 "step" 它只包含一个 "s" 所以它不符合条件。同时在匹配过程中我们忽略牌照中的大小写。
     *  
     * 
     * 示例 2：
     * 
     * 输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
     * 输出："pest"
     * 说明：存在 3 个包含字母 "s" 且有着最短长度的完整词，但我们返回最先出现的完整词。
     *  
     * 
     * 注意:
     * 
     * 牌照（licensePlate）的长度在区域[1, 7]中。
     * 牌照（licensePlate）将会包含数字、空格、或者字母（大写和小写）。
     * 单词列表（words）长度在区间 [10, 1000] 中。
     * 每一个单词 words[i] 都是小写，并且长度在区间 [1, 15] 中。
     * @param licensePlate
     * @param words
     * @return
     */
	public String shortestCompletingWord(String licensePlate, String[] words) {
		String license = licensePlate.toLowerCase().replaceAll("[0-9 ]", "");
		char[] chars = license.toCharArray();
		String ret = "";
		int size = ret.length();
		for (String word : words) {
			boolean flag = true;
			Set<Integer> idxSet = new HashSet<Integer>();
			for (int i = 0; i < chars.length; i++) {
				int idx = word.indexOf(chars[i]);
				while (idx != -1 && idxSet.contains(idx)) {
					// 牌照中可能包含多个相同的字符，比如说：对于牌照 "PP"，单词 "pair" 无法匹配，但是 "supper"可以匹配
					idx = word.indexOf(chars[i], idx + 1);
				}
				if (idx == -1) {
					flag = false;
					break;
				}
				idxSet.add(idx);
			}
			if (flag) {
				if (ret.equals("") || size > word.length()) {
					ret = word;
					size = ret.length();
				}
			}
		}
		return ret;
	}
    
    /**
     * 447. 回旋镖的数量
     * 
     * 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
     * 
     * 找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
     * 
     * 示例:
     * 
     * 输入:
     * [[0,0],[1,0],[2,0]]
     * 
     * 输出:
     * 2
     * 
     * 解释:
     * 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
     * @param points
     * @return
     */
	public int numberOfBoomerangs(int[][] points) {
		int cnt = 0;
		int len = points.length;
		for (int i = 0; i < len; i++) {
			int[] pointI = points[i];
			for (int j = 0; j < len; j++) {
				if (j == i) {
					continue;
				}
				int[] pointJ = points[j];
				for (int k = 0; k < len; k++) {
					if (k == i || k == j) {
						continue;
					}
					int[] pointK = points[k];
					int dis1 = (pointI[0] - pointJ[0]) * (pointI[0] - pointJ[0])
							+ (pointI[1] - pointJ[1]) * (pointI[1] - pointJ[1]);
					int dis2 = (pointI[0] - pointK[0]) * (pointI[0] - pointK[0])
							+ (pointI[1] - pointK[1]) * (pointI[1] - pointK[1]);
					if (dis1 == dis2) {
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
    
    /**
     * 202. 快乐数
     * 
     * 编写一个算法来判断一个数是不是“快乐数”。
     * 
     * 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
     * 
     * 示例: 
     * 
     * 输入: 19
     * 输出: true
     * 解释: 
     * 12 + 92 = 82
     * 82 + 22 = 68
     * 62 + 82 = 100
     * 12 + 02 + 02 = 1
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
    	return isHappy(n, new HashSet<Integer>());
    }
    
	private boolean isHappy(int n, Set<Integer> set) {
		if (set.contains(n)) {
			return false;
		}
		set.add(n);
		int sum = 0;
		while (n != 0) {
			sum += (n % 10) * (n % 10);
			n = n / 10;
		}
		if (sum == 1) {
			return true;
		}
		return isHappy(sum, set);
	}

	/**
     * 953. 验证外星语词典
     * 
     * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
     * 
     * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
     * 输出：true
     * 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
     * 示例 2：
     * 
     * 输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
     * 输出：false
     * 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
     * 示例 3：
     * 
     * 输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
     * 输出：false
     * 解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
     *  
     * 
     * 提示：
     * 
     * 1 <= words.length <= 100
     * 1 <= words[i].length <= 20
     * order.length == 26
     * 在 words[i] 和 order 中的所有字符都是英文小写字母。
     * @param words
     * @param order
     * @return
     */
	public boolean isAlienSorted(String[] words, String order) {
		for (int i = 1; i < words.length; i++) {
			if (!isAlienSorted(words[i - 1], words[i], order)) {
				return false;
			}
		}
		return true;
	}

	private boolean isAlienSorted(String strA, String strB, String order) {
		int lenA = strA.length();
		int lenB = strB.length();
		int idx = 0;
		while (idx < lenA && idx < lenB) {
			if (order.indexOf(strA.charAt(idx)) < order.indexOf(strB.charAt(idx))) {
				return true;
			} else if (order.indexOf(strA.charAt(idx)) == order.indexOf(strB.charAt(idx))) {
				idx++;
			} else {
				return false;
			}
		}
		if (idx < lenA) {	//A="apple",B="app"的情况
			return false;
		}
		return true;
	}
}
